Ask Question, Ask an Expert

+61-413 786 465

info@mywordsolution.com

Ask DBMS Expert


Home >> DBMS

Consider an inverted index containing, for each term, the posting list (i.e. the list of documents and occurrences within documents) for that term. The posting lists are accessed through a B+ tree with the terms serving as search keys. Each leaf of the B+ tree holds a sublist of alphabetically consecutive terms, and, with each term, a pointer to the posting list for that term.

Part a. An artificially small example of a B+ tree is shown here (pdf). (Note only part of the tree is shown in detail.) What nodes of the example B+ tree are visited to find the posting list for "dune"?

Part b. Suppose there are 2 million terms for a collection of 32 million documents of total size 200 gigabytes. We would like each internal node of the B+ tree and each leaf of the B+ tree to fit in one 8-kilobyte page of the file system. Recall that a B+ tree has a parameter m called the order of the tree, and each internal node of a B+ tree has between m+1 and 2m+1 children (except the root, which has between 2 and 2m+1). Assume that each term is represented using 16 bytes, and each pointer to a child in the tree or to a posting list is represented using 8 bytes. Find a value for the order m of the B+ tree so that one 8 kilobyte page can be assigned to each internal node and leaf, and so that an internal node will fill, but not overflow, its page when it has 2m+1 children. If you need to make additional assumptions, state what assumptions you are making.

Part c. For your m of Part b, estimate the height of the B+ tree. (Giving a range of heights is fine.) Also estimate the amount of memory needed to store the tree, including leaves but not including the posting lists themselves.

Part d. Estimate the aggregate size of the posting lists.

DBMS, Programming

  • Category:- DBMS
  • Reference No.:- M9292764

Have any Question? 


Related Questions in DBMS

Relational database design a given the following business

Relational Database Design A) Given the following business rules, identify entity types, attributes (at least two attributes for each entity, including the primary key) and relationships, and then draw an Entity-Relation ...

Assignment task -write and run sql statements to complete

Assignment Task - Write and run SQL statements to complete the following tasks Part A - DML 1. Show the details of the products where the product code starts with '22'. 2. Display the vendor details from areacode 615. 3. ...

Assignment question - write and run sql statements to

Assignment Question - Write and run SQL statements to complete the following tasks Part A - DML 1. Locate the record in the vendor table that does not have a value for the attribute V_STATE 2. Find the customers whose ba ...

The system development team at the xyz company is working

The system development team at the XYZ Company is working on developing a new customer order entry system. In the process of designing the new system, the team has identified the following data entity attributes: Invento ...

Backgrounda new training organization called abc

Background A new training organization called ABC TechTraining is opening soon and they have approached you to help design their new database. They have just completed the refurbishment of the premises and are now lookin ...

Database and information retrieval assignment - data

Database and Information Retrieval Assignment - Data Privacy Essay Task - Write an essay (aim for 750 words) that addresses issues associated with data proivacy. Use the Australian Privacy Principles - discussed in class ...

Data mining assignment -in this assignment you are asked to

Data Mining Assignment - In this assignment you are asked to explore the use of neural networks for classification and numeric prediction. You are also asked to carry out a data mining investigation on a real-world data ...

Question 1 unified communications system eg email

Question: 1. Unified Communications System (e.g., email, conferencing, and messaging) - The local area network is slower than needed, especially for newer, cloud-based applications. The email system needs refurbishment a ...

Stored procedure please create the following stored

Stored procedure. Please create the following stored routines using CPS3740_2017S database using the tables in dreamhome database. xxxx is your email id 1) Implement a stored procedure p3Q21_xxxx to display the Branch ci ...

Need an expert in the fields of system design to handle

Need an expert in the fields of system design to handle this project This is a system analysis and design project, not a research project. Refer to the list of deliverables in the instructions in the assignment to make s ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As