NDLI: Set containment join revisited

Content Provider	Springer Nature Link
Author	Bouros, Panagiotis Mamoulis, Nikos Ge, Shen Terrovitis, Malis
Copyright Year	2015
Abstract	Given two collections of set objects R and S, the $$R\bowtie _{\subseteq }S$$ set containment join returns all object pairs $$(r,s) \in R\times S$$ such that $$r\subseteq s$$ . Besides being a basic operator in all modern data management systems with a wide range of applications, the join can be used to evaluate complex SQL queries based on relational division and as a module of data mining algorithms. The state-of-the-art algorithm for set containment joins ( $$\mathtt {PRETTI}$$ ) builds an inverted index on the right-hand collection S and a prefix tree on the left-hand collection R that groups set objects with common prefixes and thus, avoids redundant processing. In this paper, we present a framework which improves $$\mathtt {PRETTI}$$ in two directions. First, we limit the prefix tree construction by proposing an adaptive methodology based on a cost model; this way, we can greatly reduce the space and time cost of the join. Second, we partition the objects of each collection based on their first contained item, assuming that the set objects are internally sorted. We show that we can process the partitions and evaluate the join while building the prefix tree and the inverted index progressively. This allows us to significantly reduce not only the join cost, but also the maximum memory requirements during the join. An experimental evaluation using both real and synthetic datasets shows that our framework outperforms $$\mathtt {PRETTI}$$ by a wide margin.
Starting Page	375
Ending Page	402
Page Count	28
File Format	PDF
ISSN	02191377
Journal	Knowledge and Information Systems
Volume Number	49
Issue Number	1
e-ISSN	02193116
Language	English
Publisher	Springer London
Publisher Date	2015-10-26
Publisher Place	London
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Set-valued data Containment join Query processing Inverted index Prefix tree Information Systems and Communication Service IT in Business
Content Type	Text
Resource Type	Article
Subject	Artificial Intelligence Information Systems Human-Computer Interaction Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient Join Processing Using Partial Precomputation

A survey of query result diversification

Query indexing with containment-encoded intervals for efficient stream processing

Alternative strategies for Performing Spatial Joins on Web Sources

Answering linear optimization queries with an approximate stream index

Extending metric index structures for efficient range query processing

Constrained recommendations for query visualizations

Efficient and scalable labeled subgraph matching using SGMatch

SEPT: an efficient skyline join algorithm on massive data

Set containment join revisited

Similar Documents

Efficient Join Processing Using Partial Precomputation

A survey of query result diversification

Query indexing with containment-encoded intervals for efficient stream processing

Alternative strategies for Performing Spatial Joins on Web Sources

Answering linear optimization queries with an approximate stream index

Extending metric index structures for efficient range query processing

Constrained recommendations for query visualizations

Efficient and scalable labeled subgraph matching using SGMatch

SEPT: an efficient skyline join algorithm on massive data

Set containment join revisited