Fast set indexing data structure for superset retrieval

Posted by Asterios on Programmers See other posts from Programmers or by Asterios
Published on 2012-11-12T10:40:03Z Indexed on 2012/11/12 17:19 UTC
Read the original article Hit count: 298

Filed under:

data-structures

|

indexing

I am given a set of sets:

{{a,b}, {a,b,c}, {a,c}, {a,c,f}}

I would like to have a data structure to index those sets such that the following "lookup" is executed fast: find all supersets of a given set.

For example, given the set {a,c} the structure would return

{{a,b,c}, {a,c,f}, {a,c}}

but not {a,b}.

Any suggestions? Could this be done with a smart trie-like data structure storing sets after a proper sorting?

This data structures is going to be queried a lot. Thus, I'm searching for a structure that might be expensive in build but rather fast to query.

© Programmers or respective owner

Related posts about data-structures

Clever ways of implementing different data structures in C & data structures that should be used mor

as seen on Stack Overflow - Search for 'Stack Overflow'
What are some clever (not ordinary) ways of implementing data structures in C, and what are some data structures that should be used more often? For example, what is the most effective way (generating minimal overhead) to implement a directed and cyclic graph with weighted edges in C? I know that… >>> More
Is there a way to track data structure dependencies from the database, through the tiers, all the way out to a web page?

as seen on Programmers - Search for 'Programmers'
When we design applications, we generally end up with the same tiered sets of data structures: A persistent data structure that is described using DDL and implemented as RDBMS tables and columns. A set of domain objects that consist primarily of data structures, usually combined with business-rule… >>> More
Why are data structures so important in interviews?

as seen on Programmers - Search for 'Programmers'
I am a newbie into the corporate world recently graduated in computers. I am a java/groovy developer. I am a quick learner and I can learn new frameworks, APIs or even programming languages within considerably short amount of time. Albeit that, I must confess that I was not so strong in data structures… >>> More
Thread-safe data structures

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I have to design a data structure that is to be used in a multi-threaded environment. The basic API is simple: insert element, remove element, retrieve element, check that element exists. The structure's implementation uses implicit locking to guarantee the atomicity of a single API call.… >>> More
Data Structures

as seen on Stack Overflow - Search for 'Stack Overflow'
There is a large stream of numbers coming in such as 5 6 7 2 3 1 2 3 .. What kind of data structure is suitable for this problem given the constraints that elements must be inserted in descending order and duplicates should be eliminated. I am not looking for any code just ideas? I was thinking… >>> More

Related posts about indexing

IIS6 Indexing Service indexing asp.net codebehind (.aspx.cs) files

as seen on Server Fault - Search for 'Server Fault'
I've setup a few catalogs on an Windows Server 2003 IIS6 install, each tracking files within a website. In the Properties - Generation Dialog for each catalog, 'Index files with unknown extensions' is turned OFF. 'Inherit above settings from Service' in that dialog is also turned off. However, the… >>> More
Outlook 2007 OST File Indexing and OneNote 2007 Indexing are Broken

as seen on Super User - Search for 'Super User'
I'm running Outlook 2007 under Windows 7 Home Premium RTM. My OST file was previously being properly indexed but eventually searches significantly slowed down so I suspected a problem. Searching and indexing appears broken in OneNote 2007 as well as search time is now significantly longer. I brought… >>> More
Indexing vs. no indexing when inserting records

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a few questions about whether or not it would be best to not use indexing. BACKGROUND: My records have a timestamp attribute, and the records will be inserted in order of their timestamps (i.e., inserted chronologically). QUESTIONS: If I DON'T use indexing is it typical for the database… >>> More
SQL SERVER – Transcript of Learning SQL Server Performance: Indexing Basics – Interview of Vinod Kumar by Pinal Dave

as seen on SQL Authority - Search for 'SQL Authority'
Recently I just wrote a blog post on about Learning SQL Server Performance: Indexing Basics and I received lots of request that if we can share some insight into the course. Here is 200 seconds interview of Vinod Kumar I took right after completing the course. We have few free codes to watch the course… >>> More
Can the Windows Indexing Service restart an app pool if it doesn't index the Web.Config?

as seen on Stack Overflow - Search for 'Stack Overflow'
I am having a slight debate with a colleague of mine on this subject. Scenario: A web site has a sub directory that is indexed using the Windows Indexing Service. There is not a web.config in this directory and the indexing service is not indexing the parent directory which is the site root. Something… >>> More