# Ext-LOUDS: A Space Efficient Extended LOUDS Index for Superset Query
## 1 Introduction  
With the rapid development in e-commerce, Internet of Things and many other fields, both the scale and complexity of data are increasing. Set is a powerful tool to express such kind of complex data. A collection of certain objects can be expressed by a set, such as commodities in a supermarket, students in a school, etc. With the increase of data scale, it is becoming a difficult task to retrieve a set in a large collection of sets. Set query mainly includes set containment query and set similarity query. The former studies whether a set contains or is contained in another set, while the latter studies the containment degree between sets. Set containment queries include subset query, superset query, and equivalent query. In this paper, we focus on superset query, that is, given a query set Q, retrieve all subsets of Q in a set dataset D (Q is the superset of these sets). Superset query is widely used in object-oriented database management systems (OODBMS) [1], job matching [2], data mining [3] and many other fields. Taking the object-oriented database management system as an example, in OODBMS, set values can be stored in attributes. A superset query algorithm can be deployed to quickly find all subsets of a given query set. For the job matching example, given a set of skills of a job seeker, a superset query can help him find all the jobs he can do. Comparing the query with each set in a large collection is infeasible. Efficient indexes are key to improving superset query performance. Inverted index [4; 5] is one of the most common indexes used in this field. [PERSON] et al. [6] designed an inverted index which scans all relevant inverted listsand counts each set ID (SID) encountered. If the count of a SID equals to the number of elements in the corresponding set of the SID, then this set is a result of the superset query. Based on this idea, a lot of efforts have been put on inverted indexes. [PERSON] et al. [7] designed an index structure combining inverted index and B-tree to improve the performance on skewed distribution. [PERSON] et al. [8] studied the problem of set containment query with error-tolerance. The main drawbacks of inverted index based algorithms lies in that they require a large number of list scan operations, thus deteriorating the query performance. Unlike inverted index, trie can compress the common prefix of sets into a single path, thereby avoiding redundant access and improving query performance. In recent years, a lot of trie based efforts can be seen in set containment query. [PERSON] et al. [9] designed an extended trie index called ETI by extending trie nodes with additional attributes to facilitate superset query. Based on this, an efficient superset query algorithm, E-Superset, is designed, which is efficient by only accessing a small number of nodes starting from the root. Although algorithms [2,10] in literature focus more on set containment join, their R-driven approach is essentially a superset query. In order to make full use of the compressed common prefixes, these algorithms usually build a partial or complete trie on dataset R, and then perform superset query for the records in dataset S to improve join efficiency. [PERSON] et al. [5] combined trie with sampling technology to make a more accurate evaluation of the cardinality of containment query results. Although trie can effectively improve the performance of superset query, it also introduces over-large space overheads [4]. For example, trie needs extra space to store the pointers pointing to the parent and child nodes of each node. In addition, to effectively support the set query, trie often needs to be extended with some attributes (e.g., the prefix set of current node [10], the link to the next node with the same label [9]) which usually are byte or integer types. These pointers and extensions will inevitably increase the overheads of trie, thereby affecting its scalability, especially when extended to large datasets.