NDLI: Performance evaluation of a parallel cascade semijoin algorithm for computing path expressions in object database systems

Content Provider	Springer Nature Link
Author	Wang, Guoren Yu, Ge
Copyright Year	2002
Abstract	With the emerging of new applications, especially in Web, such as E-Commerce, Digital Library and DNA Bank, object database systems show their stronger functions than other kinds of database systems due to their powerful representation ability on complex semantics and relationship. One distinguished feature of object database systems is path expression, and most queries on an object database are based on path expression because it is the most natural and convenient way to access the object database, for example, to navigate the hyperlinks in a web-based database. The execution of path expression is usually extremely expensive on a very large database. Therefore, the improvement of path expression execution efficiency is critical for the performance of object databases. As an important approach realizing high-performance query processing, the parallel processing of path expression on distributed object databases is explored in this paper. Up to now, some algorithms about how to compute path expressions and how to optimize path expression processing have been proposed for centralized environments. But, few approaches have been presented for computing path expressions in parallel. In this paper, a new parallel algorithm for computing path expression named Parallel Cascade Semijoin (PCSJ) is proposed. Moreover, a new scheduling strategy called right-deep zigzag tree is designed to further improve the performance of the PCSJ algorithm. The experiments have been implemented in an NOW distributed and parallel environment. The results show that the PCSJ algorithm outperforms the other two parallel algorithms (the parallel version of forward pointer chasing algorithm (PFPC) and the index splitting parallel algorithm (IndexSplit) when computing path expressions with restrictive predicates and that the right-deep zigzag tree scheduling strategy has better performance than the right-deep tree scheduling strategy.
Starting Page	140
Ending Page	151
Page Count	12
File Format	PDF
ISSN	10009000
Journal	Journal of Computer Science and Technology
Volume Number	17
Issue Number	2
e-ISSN	18604749
Language	English
Publisher	Science Press
Publisher Date	2002-01-01
Publisher Place	Beijing
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	object database path expression parallel algorithm scheduling strategy Computer Science Software Engineering Theory of Computation Data Structures, Cryptology and Information Theory Artificial Intelligence (incl. Robotics) Information Systems Applications (incl.Internet)
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computational Theory and Mathematics Computer Science Applications Software Hardware and Architecture

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

Study on Parallel Computing

Parallel algorithm design on some distributed systems

An efficient parallel graph edge matching algorithm and its applications

Tree Expressions for Information Systems

Scheduling PVM tasks

Approaches for scaling DBSCAN algorithm to large spatial databases

Semi-online scheduling with machine cost

Research on scheduling algorithms in Web cluster servers

New Model and Algorithm for Hardware/Software Partitioning

Performance evaluation of a parallel cascade semijoin algorithm for computing path expressions in object database systems

Similar Documents

Study on Parallel Computing

Parallel algorithm design on some distributed systems

An efficient parallel graph edge matching algorithm and its applications

Tree Expressions for Information Systems

Scheduling PVM tasks

Approaches for scaling DBSCAN algorithm to large spatial databases

Semi-online scheduling with machine cost

Research on scheduling algorithms in Web cluster servers

New Model and Algorithm for Hardware/Software Partitioning

Performance evaluation of a parallel cascade semijoin algorithm for computing path expressions in object database systems