4.2 Blocked sort-based indexing 69B

4.2 Blocked sort-based indexing 69
Block sizes of 8, 16, 32, and 64 kilobytes (KB) are common. We call the part
of main memory where a block being read or written BUFFER is stored a buffer.
• Data transfers fromdisk tomemory are handled by the systembus, not by
the processor. This means that the processor is available to process data
during disk I/O. We can exploit this fact to speed up data transfers by
storing compressed data on disk. Assuming an efficient decompression
algorithm, the total time of reading and then decompressing compressed
data is usually less than reading uncompressed data.
• Servers used in IR systems typically have several gigabytes (GB) of main
memory, sometimes tens of GB. Available disk space is several orders of
magnitude larger.
4.2 Blocked sort-based indexing
The basic steps in constructing a nonpositional index are depicted in Figure
1.4 (page 8). We first make a pass through the collection assembling all
term–docID pairs. We then sort the pairs with the term as the dominant key
and docID as the secondary key. Finally, we organize the docIDs for each
term into a postings list and compute statistics like term and document frequency.
For small collections, all this can be done in memory. In this chapter,
we describe methods for large collections that require the use of secondary
storage.
To make index construction more efficient, we represent terms as termIDs
TERMID (instead of strings as we did in Figure 1.4), where each termID is a unique
serial number. We can build the mapping from terms to termIDs on the fly
while we are processing the collection; or, in a two-pass approach, we compile
the vocabulary in the first pass and construct the inverted index in the
second pass. The index construction algorithms described in this chapter all
do a single pass through the data. Section 4.7 gives references to multipass
algorithms that are preferable in certain applications, for example,when disk
space is scarce.
REUTERS-RCV1 We work with the Reuters-RCV1 collection as our model collection in this
chapter, a collection with roughly 1 GB of text. It consists of about 800,000
documents that were sent over the Reuters newswire during a 1-year period
between August 20, 1996, and August 19, 1997. A typical document is
shown in Figure 4.1, but note that we ignore multimedia information like
images in this book and are only concerned with text. Reuters-RCV1 covers
a wide range of international topics, including politics, business, sports, and
(as in this example) science. Some key statistics of the collection are shown
in Table 4.2.

ผลลัพธ์ (ไทย) 1:

4.2 ถูกบล็อกเรียงตามดัชนี 69บล็อกขนาด 8, 16, 32, 64 กิโลไบต์ (KB) และใช้กันทั่วไป เราเรียกส่วนของหลักที่เป็นบล็อกการอ่าน หรือเขียนบัฟเฟอร์หน่วยความจำบัฟเฟอร์ที่จัดเก็บ•ข้อมูลโอน fromdisk tomemory จัดการ โดย systembus ไม่ใช่ตัวประมวลผล หมายความ ว่า ตัวประมวลผลการประมวลผลข้อมูลระหว่างดิสก์ I/O เราสามารถใช้ข้อเท็จจริงนี้เพื่อโอนย้ายข้อมูลด้วยความเร็วจัดเก็บบีบอัดข้อมูลบนดิสก์ สมมติว่าการบีบอัดที่มีประสิทธิภาพอัลกอริทึม การบีบอัดเวลารวมของการอ่านและขยายแล้วข้อมูลที่ได้มักจะน้อยกว่าการอ่านข้อมูลที่บีบอัด•เซิร์ฟเวอร์ที่ใช้ในระบบ IR โดยทั่วไปมีหลายกิกะไบต์ (GB) หลักหน่วยความจำ บางครั้งสิบ GB มีเนื้อที่มีหลายใบของขนาดใหญ่4.2 บล็อกเรียงตามดัชนีขั้นตอนพื้นฐานในการสร้างดัชนีแบบ nonpositional จะแสดงในรูป1.4 (หน้า 8) เราทำผ่านคอลเลกชันประกอบทั้งหมดคำ – docID คู่ เราจากนั้นเรียงลำดับจับคู่กับคำที่เป็นคีย์หลักและ docID เป็นคีย์รอง สุดท้าย เราจัด docIDs สำหรับแต่ละระยะลงในรายการบัญชี และคำนวณสถิติเช่นความถี่ระยะเวลาและเอกสารสำหรับคอลเลกชันขนาดเล็ก ทั้งหมดนี้สามารถทำในหน่วยความจำ ในบทนี้เราอธิบายวิธีการสำหรับคอลเลกชันขนาดใหญ่ที่ต้องใช้รองจัดเก็บเพื่อก่อสร้างดัชนีให้มีประสิทธิภาพมากขึ้น เราเป็นตัวแทนเงื่อนไขเป็น termIDsTERMID (แทนสายเราทำในรูป 1.4), ไม่ซ้ำกันแต่ละ termIDหมายเลขลำดับประจำสินค้า เราสามารถสร้างการแมปจากเงื่อนไขการ termIDs ในการบินในขณะที่เรากำลังประมวลผลการเรียกเก็บเงิน หรือ ในวิธีการสองรอบ เรารวบรวมคำศัพท์ในครั้งแรกผ่าน และสร้างดัชนีกลับในตัวรอบที่สอง กระบวนการก่อสร้างดัชนีที่อธิบายไว้ในบทนี้ทั้งหมดทำรอบเดียวผ่านข้อมูล 4.7 ส่วนให้อ้างอิงไปยังแหล่งอัลกอริทึมที่เหมาะกับงานบาง เช่น เมื่อดิสก์พื้นที่ขาดแคลนได้รอยเตอร์-RCV1 เราทำงานกับคอลเลกชันของรอยเตอร์ส-RCV1 เป็นคอลเลกชันของเราแบบนี้บท คอลเลกชัน มีข้อความประมาณ 1 GB ประกอบด้วยประมาณ 800000เอกสารที่ถูกส่งผ่าน newswire รอยเตอร์สในระหว่างรอบระยะเวลา 1 ปี20 สิงหาคม 1996 และ 19 สิงหาคม ปี 1997 เอกสารทั่วไปแสดงในรูป 4.1 แต่โปรดสังเกตว่าเราละเว้นข้อมูลมัลติมีเดียเช่นภาพในหนังสือและมีเฉพาะที่เกี่ยวข้องกับข้อความนี้ ครอบคลุมรอยเตอร์ส-RCV1หลากหลายหัวข้อนานาชาติ รวมทั้งการเมือง ธุรกิจ กีฬา และ(ในตัวอย่างนี้) วิทยาศาสตร์การ แสดงสถิติบางคีย์ของคอลเลกชันในตาราง 4.2

ผลลัพธ์ (ไทย) 2:

4.2 การจัดทำดัชนีบล็อคจัดเรียงตาม 69
ขนาดบล็อกของ 8, 16, 32, และ 64 กิโลไบต์ (KB) ที่อยู่ร่วมกัน ที่เราเรียกว่าเป็นส่วนหนึ่ง
ของหน่วยความจำหลักที่บล็อกการอ่านหรือเขียนบัฟเฟอร์จะถูกเก็บไว้บัฟเฟอร์.
•การถ่ายโอนข้อมูล fromdisk tomemory รับการจัดการโดย systembus ไม่ได้โดย
ตัวประมวลผล ซึ่งหมายความว่าหน่วยประมวลผลที่มีอยู่ในการประมวลผลข้อมูล
ในช่วงดิสก์ I / O เราสามารถใช้ประโยชน์จากความเป็นจริงนี้เพื่อเพิ่มความเร็วในการถ่ายโอนข้อมูลโดย
การจัดเก็บการบีบอัดข้อมูลบนดิสก์ สมมติว่าการบีบอัดที่มีประสิทธิภาพ
ขั้นตอนวิธีเวลารวมของการอ่านแล้วคลายการบีบอัด
ข้อมูลที่มักจะน้อยกว่าการอ่านการบีบอัดข้อมูล.
•เซิร์ฟเวอร์ที่ใช้ในระบบ IR มักจะมีหลายกิกะไบต์ (GB) ของหลัก
หน่วยความจำบางครั้งหลายสิบ GB เนื้อที่ว่างฮาร์ดดิสก์เป็นคำสั่งหลาย
ขนาดขนาดใหญ่.
4.2 บล็อคดัชนีเรียงตาม
ขั้นตอนพื้นฐานในการสร้างดัชนี nonpositional จะแสดงในรูปที่
1.4 (หน้า 8) ครั้งแรกที่เราทำผ่านคอลเลกชันประกอบทุก
คู่ระยะ docid จากนั้นเราจะจัดเรียงเป็นคู่ที่มีระยะเวลาเป็นคีย์ที่โดดเด่น
และ docid เป็นคีย์รอง สุดท้ายเราจัด docIDs สำหรับแต่ละ
ระยะการโพสต์ลงในรายการและคำนวณสถิติเช่นระยะและความถี่เอกสาร.
สำหรับคอลเลกชันขนาดเล็กทั้งหมดนี้สามารถทำได้ในหน่วยความจำ ในบทนี้
เราจะอธิบายวิธีการสำหรับคอลเลกชันขนาดใหญ่ที่ต้องใช้รอง
การจัดเก็บ.
เพื่อให้การก่อสร้างดัชนีมีประสิทธิภาพมากขึ้นเราเป็นตัวแทนแง่เป็น termIDs
TERMID (แทนสายที่เราทำในรูปที่ 1.4) ซึ่งแต่ละ termID เป็นเอกลักษณ์
แบบอนุกรม จำนวน เราสามารถสร้างการทำแผนที่จากแง่การ termIDs ได้ทันที
ในขณะที่เรากำลังประมวลผลการเก็บรวบรวม; หรือในวิธีการสองผ่านเรารวบรวม
คำศัพท์ผ่านครั้งแรกและสร้างดัชนีคว่ำใน
ผ่านที่สอง ขั้นตอนวิธีการก่อสร้างดัชนีอธิบายในบทนี้ทั้งหมด
ทำผ่านเดียวผ่านข้อมูล มาตรา 4.7 ช่วยให้การอ้างอิงถึงกันหลาย
ขั้นตอนวิธีการที่เป็นที่นิยมในการใช้งานบางอย่างเช่นเมื่อดิสก์
มีพื้นที่ที่ขาดแคลน.
REUTERS-RCV1 เราทำงานร่วมกับคอลเลกชันของรอยเตอร์-RCV1 เป็นคอลเลกชันของเราในรูปแบบนี้
บทคอลเลกชันที่มีประมาณ 1 GB ข้อความ . มันประกอบไปด้วยประมาณ 800,000
เอกสารที่ถูกส่งผ่านทางโทรพิมพ์สำนักข่าวรอยเตอร์ในช่วงระยะเวลา 1 ปี
ระหว่าง 20 สิงหาคม 1996 และวันที่ 19 สิงหาคม 1997 เอกสารทั่วไป
แสดงในรูปที่ 4.1 แต่ทราบว่าเราไม่สนใจข้อมูลมัลติมีเดียเช่น
ภาพใน หนังสือเล่มนี้มีความกังวลเฉพาะกับข้อความ สำนักข่าวรอยเตอร์-RCV1 ครอบคลุม
หลากหลายหัวข้อระหว่างประเทศรวมทั้งการเมืองธุรกิจกีฬาและ
(ในตัวอย่างนี้) วิทยาศาสตร์ บางสถิติที่สำคัญของคอลเลกชันที่จะแสดง
ในตารางที่ 4.2

ผลลัพธ์ (ไทย) 3:

4.2 บล็อกเรียงตามดัชนี 69
บล็อกขนาด 8 , 16 , 32 และ 64 กิโลไบต์ ( KB ) ทั่วไป เราเรียกส่วน
ของหน่วยความจำหลักที่บล็อกอ่านหรือเขียนบัฟเฟอร์จะถูกเก็บไว้บัฟเฟอร์ .
- ถ่ายโอนข้อมูล fromdisk tomemory ถูกจัดการโดยระบบไม่ได้โดย
หน่วยประมวลผล . ซึ่งหมายความว่าหน่วยประมวลผลของการประมวลผลข้อมูลใน Disk I / O
เราสามารถใช้ประโยชน์จากความจริงนี้เพื่อเพิ่มความเร็วในการถ่ายโอนข้อมูลที่บีบอัดข้อมูลที่จัดเก็บโดย
บนดิสก์ สมมติว่าขั้นตอนวิธีการบีบอัด
มีประสิทธิภาพ รวมเวลาที่อ่านแล้ว decompressing
ข้อมูลที่ถูกบีบอัดมักจะน้อยกว่าการอ่านข้อมูลที่ไม่มีการบีบอัด .
- เซิร์ฟเวอร์ที่ใช้ในระบบ IR มักจะมีหลายกิกะไบต์ ( GB ) ของหน่วยความจำหลัก
บางครั้งหลายสิบ GB ของพื้นที่ว่างในดิสก์หลายคำสั่งของ
ขนาดใหญ่ บล็อก เรียงดรรชนี

4.2 ขั้นตอนพื้นฐานในการสร้างดัชนี nonpositional เป็นที่ปรากฎในรูป
1.4 จาก ( หน้า 8 ) เราแรกให้ผ่านคอลเลกชันประกอบทั้งหมด
docid ในระยะ–คู่ เราก็เรียงคู่กับคำว่า
กุญแจเด่นและ docid เป็นคีย์รอง ในที่สุด เราจัด docids แต่ละ
ระยะเวลาในการโพสต์และคำนวณสถิติรายการเงื่อนไขและความถี่เอกสาร .
สำหรับคอลเลกชันขนาดเล็ก ทั้งหมดนี้สามารถทำได้ในหน่วยความจํา ในบทนี้เราจะอธิบายวิธีการ
คอลเลกชันขนาดใหญ่ที่ต้องใช้กระเป๋ารอง
.
ให้สร้างดัชนีมีประสิทธิภาพมากขึ้น , เราเป็นตัวแทนของเงื่อนไขที่เป็น termids
termid ( แทนของสตริงที่เราทำในรูป 1.4 ) ซึ่งแต่ละ termid เป็นเอกลักษณ์
ซีเรียลนัมเบอร์ เราสามารถสร้างแผนที่จากเงื่อนไขการ termids ในการบิน
ในขณะที่เรากำลังการประมวลผล คอลเลกชัน หรือ ในวิธีการทั้งสองเดินผ่าน เรารวบรวม
ศัพท์ในผ่านแรกและสร้างดัชนีผกผัน
ผ่าน 2 ดัชนีการก่อสร้างขั้นตอนวิธีที่อธิบายไว้ในบทนี้ทั้งหมด
ทำเดียวผ่านผ่านข้อมูล 4.7 ส่วนให้อ้างอิง multipass
ขั้นตอนวิธีที่นิยมในการใช้งานบางอย่าง ตัวอย่างเช่น เมื่อพื้นที่ดิสก์

reuters-rcv1 ขาดแคลน เราทำงานกับคอลเลกชัน reuters-rcv1 เป็นชุดรูปแบบของเราในบทนี้
, คอลเลกชันที่มีประมาณ 1 GB ของข้อความ ประกอบด้วยเรื่อง 800000
เอกสารที่ถูกส่งผ่านข่าวรอยเตอร์ ในช่วงระยะเวลา 1 ปี
ระหว่าง 20 สิงหาคม , 19 สิงหาคม 2539 และ 2540เอกสารทั่วไปคือ
แสดงในรูปที่ 4.1 แต่ทราบว่าเราไม่สนใจข้อมูลมัลติมีเดียเช่น
ภาพในหนังสือเล่มนี้ และจะเกี่ยวข้องกับข้อความ
reuters-rcv1 ครอบคลุมหลากหลายของหัวข้อที่ต่างประเทศ รวมทั้งการเมือง ธุรกิจ กีฬา และ
( เช่นในตัวอย่างนี้ ) วิทยาศาสตร์ บางสถิติที่สำคัญของคอลเลกชันแสดง
ตารางที่ 4.2 .