Article

A parallel index for semistructured data

Authors:

Brian F. Cooper,

Neal Sample,

Moshe ShadmonAuthors Info & Claims

SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

Pages 890 - 896

https://doi.org/10.1145/508791.508963

Published: 11 March 2002 Publication History

Get Access

Abstract

Database systems are increasingly being used to manage semistructured data, which may not have a fixed structure or set of relationships between data items. Indexes which use tree structures to manage semistructured data become unbalanced and difficult to parallelize due to the complex nature of the data. We propose a mechanism by which an unbalanced vertical tree is managed in a balanced way by additional layers of horizontal index. Then, the vertical tree can be partitioned among parallel computing nodes in a balanced fashion. We discuss how to construct, search and update such a horizontal structure using the example of a Patricia trie index. We also present simulation results that demonstrate the speedup offered by such parallelism, for example, with three-way parallelism, our techniques can provide almost a factor of three speedup.

References

[1]

DBLP computer science bibliography. http://www.informatik.uni-trier.de/-ley/db/.

Google Scholar

[2]

Serge Abiteboul. Querying semi-structured data. In Proc. ICDT, 1997.

Digital Library

Google Scholar

[3]

Barbara T. Blaustein and Charles W. Kaufman. Updating replicated data during communications failures. In Proc. VLDB, pages 49-58, 1985.

Google Scholar

[4]

D. Comer. The ubiquitous b-tree. Computing Surveys, 11(2):121-137, 1979.

Digital Library

Google Scholar

[5]

Brian Cooper and Moshe Shadmon. The Index Fabric: A mechanism for indexing and querying the same data in many different ways, 2000. RightOrder Incorporated Technical Report.

Google Scholar

[6]

Alin Deutsch, Mary Fernandez, and Dan Suciu. Storing semistructured data with STORED. In Proc. SIGMOD, 1999.

Digital Library

Google Scholar

[7]

David J. DeWitt and Jim Gray. Parallel database systems: The future of high performance database systems. CACM, 35(6):85-98, 1992.

Digital Library

Google Scholar

[8]

A. A. Diwan, Sanjeeva Rane, S. Seshadri, and S. Sudarshan. Clustering techniques for minimizing external path length. In Proc. VLDB, pages 342-353, 1996.

Digital Library

Google Scholar

[9]

Brian Cooper et al. A fast index for semistructured data. In Proc. VLDB, September 2001.

Digital Library

Google Scholar

[10]

Jason McHugh et al. Lore: A database management system for semistructured data. SIGMOD Record, 26(3):54-66, September 1997.

Digital Library

Google Scholar

[11]

D. Gifford. Weighted voting for replicated data. In Proc. SOSP, pages 49-58, 1979.

Digital Library

Google Scholar

[12]

Joseph M. Hellerstein, Jeffrey F. Naughton, and Avi Pfeffer. Generalized search trees for database systems. In Proc. VLDB, pages 562-573, September 1995.

Digital Library

Google Scholar

[13]

Donald Knuth. The Art of Computer Programming, Vol. III, Sorting and Searching, Third Edition. Addison Wesley, Reading, MA, 1998.

Digital Library

Google Scholar

[14]

M. Tamer Ozsu and Patrick Valduriez. Principles of Distributed Database Systems (Second Edition). Prentice Hall, Upper Saddle River, New Jersey, 1999.

Digital Library

Google Scholar

Cited By

View all

Wellenzohn KBöhlen MHelmer SPietri AZacchiroli S(2022)Robust and scalable content-and-structure indexingThe VLDB Journal10.1007/s00778-022-00764-y32:4(689-715)Online publication date: 15-Oct-2022
https://doi.org/10.1007/s00778-022-00764-y
Al-Obaidi A(2021)Design and Implementation of a Computerized Library Management System Using GUINext Generation of Internet of Things10.1007/978-981-16-0666-3_55(669-683)Online publication date: 15-Jun-2021
https://doi.org/10.1007/978-981-16-0666-3_55
Kim JKim H(2019)A partition index for XML and semi-structured dataData & Knowledge Engineering10.1016/j.datak.2004.06.00151:3(349-368)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.datak.2004.06.001
Show More Cited By

Index Terms

A parallel index for semistructured data

Recommendations

Data-Parallel Programming on MIMD Computers

The implementation of two compilers for the data-parallel programming language Dataparallel C is described. One compiler generates code for Intel and nCUBE hypercube multicomputers; the other generates code for Sequent multiprocessors. A suite of ...
Communicating Data-Parallel Tasks: An MPI Library for HPF
HIPC '96: Proceedings of the Third International Conference on High-Performance Computing (HiPC '96)

High Performance Fortran (HPF) has emerged as a standard dialect of Fortran for data-parallel computing. However, HPF does not support task parallelism or heterogeneous computing adequately. This paper presents a summary of our work on a library-based ...
Global parallel index for multi-processors database systems

In this paper, we propose a global B<sup>+</sup> indexing tree structure for parallel database systems. A global B<sup>+</sup> indexing tree is a tree structure used for indexing where the complete index tree is partially partitioned into multi-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SAC '02: Proceedings of the 2002 ACM symposium on Applied computing

March 2002

1200 pages

ISBN:1581134452

DOI:10.1145/508791

Conference Chair:
Gary B. Lamont
Air Force Institute of Technology, USA
,
Program Chairs:
Hisham Haddad
Kennesaw State Univ., USA
,
George Papadopoulos
Univ. of Cyprus, Cyprus
,
Publications Chair:
Brajendra Panda
University of Arkansas, USA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SAC02

Sponsor:

SIGAPP

SAC02: 2002 ACM Symposium on Applied Computing

March 11 - 14, 2002

Madrid, Spain

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
412
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wellenzohn KBöhlen MHelmer SPietri AZacchiroli S(2022)Robust and scalable content-and-structure indexingThe VLDB Journal10.1007/s00778-022-00764-y32:4(689-715)Online publication date: 15-Oct-2022
https://doi.org/10.1007/s00778-022-00764-y
Al-Obaidi A(2021)Design and Implementation of a Computerized Library Management System Using GUINext Generation of Internet of Things10.1007/978-981-16-0666-3_55(669-683)Online publication date: 15-Jun-2021
https://doi.org/10.1007/978-981-16-0666-3_55
Kim JKim H(2019)A partition index for XML and semi-structured dataData & Knowledge Engineering10.1016/j.datak.2004.06.00151:3(349-368)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/j.datak.2004.06.001
Li SZhu J(2014)A XML Pattern Match Algorithm of Structural IndexApplied Mechanics and Materials10.4028/www.scientific.net/AMM.513-517.1507513-517(1507-1510)Online publication date: 6-Feb-2014
https://doi.org/10.4028/www.scientific.net/AMM.513-517.1507
Li DLu XHuang XChen W(2013)Structural Join in the ‘XSQS’ Native XML DatabaseJournal of Software10.4304/jsw.8.1.200-2078:1Online publication date: 21-Jan-2013
https://doi.org/10.4304/jsw.8.1.200-207
Zhang BZou D(2013)Efficient Detection for Top Part of Research Paper with Layout IndexApplied Mechanics and Materials10.4028/www.scientific.net/AMM.427-429.2383427-429(2383-2386)Online publication date: Sep-2013
https://doi.org/10.4028/www.scientific.net/AMM.427-429.2383
Zhang BZhuang Z(2012)Efficient Structural XML Index for Multiple QueriesRecent Advances in Computer Science and Information Engineering10.1007/978-3-642-25781-0_64(423-431)Online publication date: 2012
https://doi.org/10.1007/978-3-642-25781-0_64
Kruliš MYaghob J(2010)The Location Path to Hell Is Paved With Unoptimized Axes: XPath Implementation TipsNetworked Digital Technologies10.1007/978-3-642-14306-9_47(474-487)Online publication date: 2010
https://doi.org/10.1007/978-3-642-14306-9_47
Aggarwal CWang H(2010)Graph Data Management and Mining: A Survey of Algorithms and ApplicationsManaging and Mining Graph Data10.1007/978-1-4419-6045-0_2(13-68)Online publication date: 18-Jan-2010
https://doi.org/10.1007/978-1-4419-6045-0_2
Aiso SYahagi T(2009)Iryo To Shakai10.4091/iken.19.13119:2(131-140)Online publication date: 2009
https://doi.org/10.4091/iken.19.131
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Data-Parallel Programming on MIMD Computers

Communicating Data-Parallel Tasks: An MPI Library for HPF

Global parallel index for multi-processors database systems