{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/90645"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/90645","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Template B+ trees: an index scheme for fast data streams with distributed append-only stores","abstract":"Distributed systems are now commonly used to manage massive data flooding from the physical world, such as user-generated content from online social media and communication records from mobile phones. The new generation of distributed data management systems, such as HBase, Cassandra and Riak, are designed to perform queries and tuple insertions only. Other database operations such as deletions and updates are simulated by appending the keys associated with the target tuples to operation logs. Such an append-only store architecture maximizes the processing throughput on incoming data, but potentially incurs higher costs during query processing, because additional computation is needed to generate consistent snapshots of the database. Indexing is the key to enable efficient query processing by fast data retrieval and aggregation under such a system architecture. This thesis presents a new in-memory indexing scheme for distributed append-only stores. Our new scheme utilizes traditional index structures based on B+ trees and their variants to create an efficient in-memory template-based tree without the overhead of expensive node splits. We also propose the use of optimized domain partitioning and multi-thread insertion techniques to exploit the advantages of the template B+ tree structure. Our empirical evaluations show that insertion throughput is five times higher with template B+ trees than with HBase, on a variety of real and synthetic workloads.","abstract_html":"Distributed systems are now commonly used to manage massive data flooding from the physical world, such as user-generated content from online social media and communication records from mobile phones. The new generation of distributed data management systems, such as HBase, Cassandra and Riak, are designed to perform queries and tuple insertions only. Other database operations such as deletions and updates are simulated by appending the keys associated with the target tuples to operation logs. Such an append-only store architecture maximizes the processing throughput on incoming data, but potentially incurs higher costs during query processing, because additional computation is needed to generate consistent snapshots of the database. Indexing is the key to enable efficient query processing by fast data retrieval and aggregation under such a system architecture. This thesis presents a new in-memory indexing scheme for distributed append-only stores. Our new scheme utilizes traditional index structures based on B+ trees and their variants to create an efficient in-memory template-based tree without the overhead of expensive node splits. We also propose the use of optimized domain partitioning and multi-thread insertion techniques to exploit the advantages of the template B+ tree structure. Our empirical evaluations show that insertion throughput is five times higher with template B+ trees than with HBase, on a variety of real and synthetic workloads.","abstract_has_math":false,"creators":["Mazumdar, Parijat"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Winslett, Marianne"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2016,"date_issued":"2016-07-07T19:57:59Z","date_published":"2016-07-07T19:57:59Z","updated_at":"2026-07-22T22:26:34Z","subjects":["B+ trees","Template B+ Trees","distributed","append-only datastore"],"languages":["en"],"rights":["Copyright 2016 Parijat Mazumdar"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/90645","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Winslett, Marianne"]},{"key":"dc:creator","label":"Author","values":["Mazumdar, Parijat"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2016-07-07T19:57:59Z","2016-04-26","2016-05"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["B+ trees","Template B+ Trees","distributed","append-only datastore"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2016 Parijat Mazumdar"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/90645"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Distributed systems are now commonly used to manage massive data flooding from the physical world, such as user-generated content from online social media and communication records from mobile phones. The new generation of distributed data management systems, such as HBase, Cassandra and Riak, are designed to perform queries and tuple insertions only. Other database operations such as deletions and updates are simulated by appending the keys associated with the target tuples to operation logs. Such an append-only store architecture maximizes the processing throughput on incoming data, but potentially incurs higher costs during query processing, because additional computation is needed to generate consistent snapshots of the database. Indexing is the key to enable efficient query processing by fast data retrieval and aggregation under such a system architecture. This thesis presents a new in-memory indexing scheme for distributed append-only stores. Our new scheme utilizes traditional index structures based on B+ trees and their variants to create an efficient in-memory template-based tree without the overhead of expensive node splits. We also propose the use of optimized domain partitioning and multi-thread insertion techniques to exploit the advantages of the template B+ tree structure. Our empirical evaluations show that insertion throughput is five times higher with template B+ trees than with HBase, on a variety of real and synthetic workloads.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Parijat Mazumdar, accepted the attached license on 2016-04-25 at 12:45.","The student, Parijat Mazumdar, submitted this Thesis for approval on 2016-04-25 at 12:51.","This Thesis was approved for publication on 2016-04-26 at 15:46.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9473 on 2016-07-07 at 13:32:59","Made available in DSpace on 2016-07-07T19:57:59Z (GMT). No. of bitstreams: 2 MAZUMDAR-THESIS-2016.pdf: 969810 bytes, checksum: 564b6f7c7a110848351527e924c2fa38 (MD5) LICENSE.txt: 4213 bytes, checksum: 9594c9e2496e94ac06d23595dea12b7b (MD5) Previous issue date: 2016-04-26"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Template B+ trees: an index scheme for fast data streams with distributed append-only stores"]}]}],"canonical_facts":{"dc:contributor":["Winslett, Marianne"],"dc:creator":["Mazumdar, Parijat"],"dc:date":["2016-07-07T19:57:59Z","2016-04-26","2016-05"],"dc:description":["Distributed systems are now commonly used to manage massive data flooding from the physical world, such as user-generated content from online social media and communication records from mobile phones. The new generation of distributed data management systems, such as HBase, Cassandra and Riak, are designed to perform queries and tuple insertions only. Other database operations such as deletions and updates are simulated by appending the keys associated with the target tuples to operation logs. Such an append-only store architecture maximizes the processing throughput on incoming data, but potentially incurs higher costs during query processing, because additional computation is needed to generate consistent snapshots of the database. Indexing is the key to enable efficient query processing by fast data retrieval and aggregation under such a system architecture. This thesis presents a new in-memory indexing scheme for distributed append-only stores. Our new scheme utilizes traditional index structures based on B+ trees and their variants to create an efficient in-memory template-based tree without the overhead of expensive node splits. We also propose the use of optimized domain partitioning and multi-thread insertion techniques to exploit the advantages of the template B+ tree structure. Our empirical evaluations show that insertion throughput is five times higher with template B+ trees than with HBase, on a variety of real and synthetic workloads.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2016-07-07 without embargo terms","The student, Parijat Mazumdar, accepted the attached license on 2016-04-25 at 12:45.","The student, Parijat Mazumdar, submitted this Thesis for approval on 2016-04-25 at 12:51.","This Thesis was approved for publication on 2016-04-26 at 15:46.","DSpace SAF Submission Ingestion Package generated from Vireo submission #9473 on 2016-07-07 at 13:32:59","Made available in DSpace on 2016-07-07T19:57:59Z (GMT). No. of bitstreams: 2 MAZUMDAR-THESIS-2016.pdf: 969810 bytes, checksum: 564b6f7c7a110848351527e924c2fa38 (MD5) LICENSE.txt: 4213 bytes, checksum: 9594c9e2496e94ac06d23595dea12b7b (MD5) Previous issue date: 2016-04-26"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/90645"],"dc:language":["en"],"dc:rights":["Copyright 2016 Parijat Mazumdar"],"dc:subject":["B+ trees","Template B+ Trees","distributed","append-only datastore"],"dc:title":["Template B+ trees: an index scheme for fast data streams with distributed append-only stores"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:34Z"}