Ext-LOUDS: A Space Efficient Extended LOUDS Index for Superset Query
Source abstract
Abstract
Superset query is widely used in object-oriented databases, data mining, and many other fields. Trie is an efficient index for superset query, whereas most existing trie index aim at improving query performance while ignoring storage overheads. To solve this problem, in this paper, we propose an efficient extended Level-Ordered Unary Degree Sequence (LOUDS) index: Ext-LOUDS. Ext-LOUDS expresses a trie by 1 integer vector and 3 bit vectors directly map each NodeID to its corresponding position, thus accelerating some key operations needed for superset query. Based on Ext-LOUDS, an efficient superset query algorithm, ELOUDS-Super, is designed. Experimental results on both real and synthetic datasets show that Ext-LOUDS can decrease 50%–60% space overheads compared with trie while maintaining a relative good query performance.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Data Management and Algorithms · Algorithms and Data Compression · Advanced Database Systems and Queries
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
Yunnan Key Laboratory of Artificial Intelligence, Kunming University of Science and Technology, Kunming 650500, China
School of Computing, Informatics, and Decision Systems, Arizona State University, Tempe, AZ 85287, USA
Funding
China Scholarship Council · National Natural Science Foundation of China · the National Key Research and Development Program of China
References (25)
Show source-provided references
1. Savnik, I. (2013, January 2–6). Index Data Structure for Fast Subset and Superset Queries. Proceedings of the International Conference on Availability, Reliability, and Security, Regensburg, Germany.10.1007/978-3-642-40511-2_10 ↗
2. Deng, D., Yang, C., and Shang, S. (2019, January 8–11). LCJoin: Set Containment Join via List Crosscutting. Proceedings of the IEEE 35th International Conference on Data Engineering (ICDE), Macau, China.10.1109/ICDE.2019.00040 ↗
3. Set containment join revisited10.1007/s10115-015-0895-7 ↗
4. FreshJoin: An Efficient and Adaptive Algorithm for Set Containment Join10.1007/s41019-019-00107-y ↗
5. Yang, Y., Zhang, W., Zhang, Y., Lin, X., and Wang, L. (2019). Selectivity Estimation on Set Containment Search, Springer.10.1007/978-3-030-18576-3_20 ↗
6. A performance study of four index structures for set-valued attributes of low cardinality10.1007/s00778-003-0106-0 ↗
7. Terrovitis, M., Bouros, P., Vassiliadis, P., Sellis, T.K., and Mamoulis, N. (2011, January 21–24). Efficient answering of set containment queries for skewed item distributions. Proceedings of the International Conference on Edbt, Uppsala, Sweden.10.1145/1951365.1951394 ↗
8. Agrawal, P., Arasu, A., and Kaushik, R. (2010, January 6–10). On indexing error-tolerant set containment. Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, IN, USA.10.1145/1807167.1807267 ↗
9. Jia, L. (2012). Research on Set Similarity and Set Containtment in Main Memory Database, South China University of Technology. (In Chinese).
10. Yang, J., Zhang, W., Yang, S., Zhang, Y., and Lin, X. (2017, January 19–22). TT-Join: Efficient Set Containment Join. Proceedings of the IEEE International Conference on Data Engineering, San Diego, CA, USA.10.1109/ICDE.2017.107 ↗
11. An Efficient Digital Search Algorithm by Using a Double-Array Structure10.1109/32.31365 ↗
12. Jia, L., Zhang, C., Li, M., Chen, Y., and Ding, J. (2020). An Efficient Two-Level-Partitioning-Based Double Array and Its Parallelization. Appl. Sci., 10.10.3390/app10155266 ↗
13. Jacobson, G. (November, January 30). Space-efficient static trees and graphs. Proceedings of the Symposium on Foundations of Computer Science, Research Triangle Park, NC, USA.
14. Delpratt, O.N., Rahman, N., and Raman, R. (2006). Engineering the LOUDS Succinct Tree Representation, Springer.10.1007/11764298_12 ↗
15. Succinct Range Filters10.1145/3375660 ↗
16. Compression of double array structures for fixed length keywords10.1016/j.ipm.2014.04.004 ↗
17. A compression method of double-array structures using linear functions10.1007/s10115-015-0873-0 ↗
18. Zhou, D., Andersen, D.G., and Kaminsky, M. (2013). Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences, Springer.10.1007/978-3-642-38527-8_15 ↗
19. Navarro, G., and Providel, E. (2012). Fast, Small, Simple Rank/Select on Bitmaps, Springer.10.1007/978-3-642-30850-5_26 ↗
20. Ermanno Pibiri, G., and Kanda, S. (2020). Rank/Select Queries over Mutable Bitmaps. arXiv, Available online: https://arxiv.org/abs/2009.12809.10.1016/j.is.2021.101756 ↗
21. He, M., Munro, J.I., Nekrich, Y., Wild, S., and Wu, K. (2020). Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees. arXiv, Available online: https://arxiv.org/abs/2005.07644.
22. Navarro, G., and Ord’On˜Ez, A. (2014). Grammar Compressed Sequences with Rank/Select Support. International Symposium on String Processing and Information Retrieval, Springer.10.1007/978-3-319-11918-2_4 ↗
23. High-Order Entropy Compressed Bit Vectors with Rank/Select10.3390/a7040608 ↗
24. The UCI KDD archive of large data sets for data mining research and experimentation10.1145/380995.381030 ↗
25. Ley, M. (2002, January 11–13). The DBLP Computer Science Bibliography: Evolution, Research Issues, Perspectives. Proceedings of the String Processing & Information Retrieval, International Symposium, Spire, Lisbon, Portugal.10.1007/3-540-45735-6_1 ↗