We can do better than Θ(T2/n) by in

We can do better than Θ(T
2/n) by introducing log2
(T/n) indexes I0, I1
,
I2, . . . of size 20 × n, 21 × n, 22 × n . . . . Postings percolate up this sequence of indexes and are processed only once on each level. This scheme is called log-arithmic merging (Figure 4.7). As before, up to n postings are accumulated in
an in-memory auxiliary index, which we call Z0. When the limit n is reached,
the 20 × n postings in Z0 are transferred to a new index I0 that is created on
disk. The next time Z0 is full, it is merged with I0 to create an index Z1 of size
2
1× n. Then Z1
is either stored as I1
(if there isn’t already an I1
) or merged with I1 into Z2 (if I1 exists); and so on. We service search requests by query-ing in-memory Z0 and all currently valid indexes Ii on disk and merging the
results. Readers familiar with the binomial heap data structure2 will recog-nize its similarity with the structure of the inverted indexes in logarithmic
merging

Results (Thai) 1:

เราสามารถทำดีกว่า Θ(T
2/n) โดยการแนะนำ log2
(T/n) ดัชนี I0, I1
,
I2,...ของขนาด 20 × n การ 21 × n, n 22 ×... ลง percolate ค่าดัชนีลำดับนี้ และประมวลผลเพียงครั้งเดียวในแต่ละระดับ โครงร่างนี้เรียกว่าล็อก-arithmic ผสาน (รูป 4.7) เป็นมาก่อน ได้ลง n แล้วสะสมใน
ในหน่วยความจำเสริมดัชนี ซึ่งเราเรียก Z0 เมื่อถึงขีดจำกัด n,
20 × n ลงใน Z0 ถูกโอนย้ายไปดัชนีใหม่ I0 ที่สร้างบน
ดิสก์ ครั้ง Z0 เต็ม มันรวมกับ I0 สร้างดัชนี Z1 ขนาด
2
1 × n แล้ว Z1
หรือจัดเก็บเป็น I1
(ถ้าไม่มีเป็น I1
) หรือผสานกับ I1 เป็น Z2 (ถ้า I1); และอื่น ๆ บริการรับคำขอการค้นหา โดย Z0 ในหน่วยความจำแบบสอบถาม-ing และดัชนีทั้งหมดถูกต้องปัจจุบัน Ii บนดิสก์และการผสานการ
ผลลัพธ์ที่ ผู้อ่านที่คุ้นเคยกับการ structure2 ข้อมูลกองทวินามจะ recog nize ที่คล้ายคลึงกับโครงสร้างของดัชนีกลับในลอการิทึม
ผสาน

Results (Thai) 2:

เราสามารถทำได้ดีกว่าΘ (T
2 / n) โดยการแนะนำ log2
(T / n) ดัชนี I0, I1
,
I2, . . ขนาด 20 × n, 21 × n, 22 × n . . . โพสต์ไหลผ่านขึ้นตามลำดับของดัชนีนี้และมีการประมวลผลได้เพียงครั้งเดียวในแต่ละระดับ โครงการนี้เรียกว่าการรวมเข้าสู่ระบบ arithmic (รูปที่ 4.7) ในขณะที่ก่อนที่จะถึงการโพสต์ n จะสะสมอยู่ใน
ดัชนีในหน่วยความจำเสริมที่เราเรียก Z0 เมื่อถึงขีด จำกัด n ถึง
20 × n โพสต์ใน Z0 จะถูกโอนไป I0 ดัชนีใหม่ที่ถูกสร้างขึ้นบน
ดิสก์ ครั้งต่อไปที่ Z0 เต็มจะรวมกับ I0 สร้างดัชนี Z1 ขนาด
2
1 × n แล้ว Z1
เป็นทั้งเก็บไว้เป็น I1
(ถ้ามีไม่ได้ I1
) หรือรวมกับ I1 เป็น Z2 (ถ้ามีอยู่ I1); และอื่น ๆ เราให้บริการการร้องขอการค้นหาโดยใช้แบบสอบถามไอเอ็นจีในหน่วยความจำ Z0 และดัชนีที่ถูกต้องในปัจจุบัน Ii บนดิสก์และการรวม
ผล ผู้อ่านคุ้นเคยกับทวินามกอง structure2 ข้อมูลจะ recog-nize คล้ายคลึงกับโครงสร้างของดัชนีคว่ำในลอการิทึม
รวม

Results (Thai) 3:

เราทำได้ดีกว่าΘ ( t
2 / n ) โดยการแนะนำ LOG
( t / n ) i1 i1
,
) , I2 , . . . . . . . . ขนาด 20 × N 21 × N 22 × N . . . . . . . . . โพสต์กรองขึ้นลำดับดัชนีและประมวลผลเพียงครั้งเดียวในแต่ละระดับ โครงการนี้เรียกว่าเข้าสู่ระบบ arithmic ผสาน ( รูปที่ 1 ) ก่อนถึง n ประกาศจะสะสมใน
ในหน่วยความจำเสริมดัชนี ซึ่งเราเรียก z0 . เมื่อขีด N ถึง
โพสต์ใน 20 × N z0 จะส่งไปใหม่ดัชนี i0
ที่ถูกสร้างขึ้นบนดิสก์ คราวหน้า z0 เต็ม มันผสานกับการสร้างดัชนีได้ขนาด Z1
2
1 × N . แล้ว Z1
คือให้เก็บเป็น i0
( ถ้าไม่มีก็ i0
) หรือรวมเข้ากับ i0 ในเซสท์แอร์เวย์ ( ถ้ามันมี ) ; และ เราบริการหน้าค้นหาโดยค้นหาไอเอ็นจีใน z0 หน่วยความจำและขณะนี้ถูกต้องดัชนี II บนดิสก์และการรวม
ผลลัพธ์ ผู้อ่านที่คุ้นเคยกับทวินามกองข้อมูล structure2 จะ recog nize ของความเหมือนกับโครงสร้างของดัชนีในการผสาน

แบบลอการิทึม