✖

HyperLogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกันอย่างแม่นยำ

ชุดบทความเรื่องขั้นตอนวิธีสำหรับประมาณจำนวนค่าที่ไม่ซ้ำกันในมัลติเซตดำเนินต่อด้วยบทความเรื่องขั้นตอนวิธีระดับ state of the art คือ HyperLogLog อย่างไรก็ตาม แนวคิดทั้งหมดของขั้นตอนวิธีนี้มาจาก LogLog ที่อธิบายไว้ก่อนหน้า ดังนั้นก่อนอ่านต่อ ควรเข้าใจ LogLog ให้ดีก่อน

ขั้นตอนวิธี LogLog มีปัญหาหลักสองข้อ:

ค่านอกเกณฑ์

ค่าประมาณสุดท้ายของ LogLog ไวต่อค่านอกเกณฑ์ (outlier) มาก ซึ่งคือค่าที่อยู่ห่างจากค่าอื่น ๆ มาก โดยทั่วไปความยาวสูงสุดของส่วนท้ายที่เป็นศูนย์ของแต่ละกลุ่มส่วนใหญ่จะใกล้เคียงกัน เช่น อยู่ระหว่าง 12 ถึง 15 แต่แล้วก็มีส่วนท้ายที่เป็นศูนย์อันหนึ่งยาวถึง 27 ผลต่างขนาดใหญ่นี้ทำให้ค่าประมาณจำนวนค่าที่ไม่ซ้ำกันยุ่งเหยิง เพราะค่าเฉลี่ยเลขคณิตตามปกติรับมือกับกรณีนี้ได้ไม่ดีนัก โดยพื้นฐานแล้วเป็นหลักการเดียวกับที่ผู้บริหารระดับสูงไม่กี่คนที่มีเงินเดือนสูงทำให้เงินเดือนเฉลี่ยของทั้งประเทศสูงขึ้น

ผู้คิดค้นขั้นตอนวิธีพยายามแก้ปัญหานี้โดยตัดค่านอกเกณฑ์ทิ้ง คือไม่นำค่าสูงสุดที่มากที่สุดบางค่ามาคิดค่าเฉลี่ย แต่วิธีนี้ไม่ค่อยดีนัก ต่อมาจึงลองอีกวิธีหนึ่ง คือใช้ค่าเฉลี่ยฮาร์มอนิกแทนค่าเฉลี่ยเลขคณิต ซึ่งมีสมบัติดีกว่ามากเมื่อมีค่าที่อยู่ห่างจากค่าเฉลี่ย

ผลลัพธ์ที่แย่มากเมื่อคาร์ดินัลลิตีมีค่าน้อย

LogLog ให้ผลลัพธ์ที่แย่มากเมื่อต้องประมาณคาร์ดินัลลิตีของมัลติเซตขนาดเล็ก ถ้ามัลติเซตมีสมาชิกที่ไม่ซ้ำกันเพียงไม่กี่ตัว LogLog จะให้ค่าประมาณที่มากเกินจริงอย่างไร้เหตุผล ผู้คิดค้นแก้ปัญหานี้อย่างแยบยล คือเมื่อข้อมูลขาเข้าเป็นมัลติเซตที่มีคาร์ดินัลลิตีต่ำ จะไม่ใช้ขั้นตอนวิธี LogLog แต่ใช้ขั้นตอนวิธีอื่นโดยสิ้นเชิง ได้แก่ Linear counting ที่คุ้นเคย แต่จะรู้ได้อย่างไรว่าข้อมูลขาเข้าเป็นมัลติเซตที่มีคาร์ดินัลลิตีต่ำ ในเมื่อยังไม่รู้คาร์ดินัลลิตี

ให้ LogLog ประมาณจำนวนสมาชิกที่ไม่ซ้ำกันก่อน ถ้าพบว่าค่าประมาณนี้ค่อนข้างต่ำ ก็ทิ้งค่าประมาณนั้นแล้วคำนวณใหม่ด้วยขั้นตอนวิธี Linear counting ทบทวนสั้น ๆ ว่า Linear counting ทำงานอย่างไร ตอนเริ่มต้นจองอาร์เรย์ (บิต) ที่เป็นศูนย์ทั้งหมดซึ่งมีขนาดกำหนดไว้ล่วงหน้า โดยทั่วไปเป็นกำลังของสอง ไล่ดูสมาชิกทุกตัวของมัลติเซต คำนวณค่าแฮชของแต่ละตัว แล้วแปลงเป็นจำนวนเต็ม i ตั้งแต่ 0 ถึงความยาวของอาร์เรย์ลบหนึ่ง จากนั้นเขียนเลข 1 ลงในอาร์เรย์ที่ดัชนี i ท้ายสุดนับจำนวนศูนย์และหนึ่งในอาร์เรย์ แล้วใช้สูตรง่าย ๆประมาณคาร์ดินัลลิตี

แต่ขั้นตอนวิธี LogLog ไม่ได้ใช้อาร์เรย์บิตสำหรับ “เก็บ” ค่าแฮชที่คำนวณได้ แต่ใช้อาร์เรย์ที่เก็บความยาวสูงสุดของส่วนท้าย อาร์เรย์อาจเป็นดังนี้:

[2, 5, 9, 0, 5, 4, 4, 0]

โดยแต่ละจำนวนแทนความยาวสูงสุดของส่วนท้ายที่เป็นศูนย์ในกลุ่มของค่าแฮชกลุ่มนั้น ค่าที่ไม่เป็นศูนย์ในตำแหน่งที่ i ย่อมหมายความว่าในมัลติเซตมีสมาชิกที่ค่าแฮช (สามบิต) เท่ากับ i กล่าวอีกอย่างคือ แปลงอาร์เรย์นี้เป็นอาร์เรย์บิตสำหรับ linear counting ได้โดยคงศูนย์ไว้และเปลี่ยนจำนวนบวกใด ๆ เป็นหนึ่ง จากอาร์เรย์ข้างต้นจะได้อาร์เรย์บิต:

[1, 1, 1, 0, 1, 1, 1, 0]

ตอนนี้ใช้ขั้นตอนวิธี Linear counting ประมาณคาร์ดินัลลิตีได้แล้ว

แต่มีจุดที่ต้องระวังอยู่ข้อหนึ่ง ในอาร์เรย์เก็บส่วนท้ายที่เป็นศูนย์ที่ยาวที่สุด แล้วถ้าในกลุ่มหนึ่งค่าแฮชทุกค่าลงท้ายด้วยเลข 1 ล่ะ เช่น ถ้าใช้สามบิตสุดท้ายเป็นตัวระบุกลุ่มของค่าแฮช ความยาวของส่วนท้ายที่เป็นศูนย์ของค่าแฮช “01001100” จะเป็นศูนย์ เพราะเวกเตอร์ “01001” ลงท้ายด้วยเลข 1 จึงต้องเก็บศูนย์ลงในอาร์เรย์ของค่าสูงสุดที่ดัชนี 4 (1002=410) แต่ใน linear counting ค่านี้จะหมายความว่าไม่พบค่าใดที่มีค่าแฮชเป็นสี่ ซึ่งไม่เป็นความจริง

จึงปรับขั้นตอนวิธีให้เก็บในอาร์เรย์ของค่าสูงสุดไม่ใช่ความยาวของส่วนท้ายที่เป็นศูนย์ที่ยาวที่สุด แต่เป็นดัชนีของ “เลข 1 ตัวแรกจากทางขวา” (นับดัชนีเริ่มจากหนึ่ง) ซึ่งเท่ากับความยาวของส่วนท้ายที่เป็นศูนย์บวกหนึ่ง ด้วยวิธีนี้ ศูนย์ที่ดัชนี i จะหมายความว่าไม่มีค่าใดที่มีค่าแฮชเท่ากับ i และใช้อาร์เรย์เช่นนี้กับ linear counting ได้

การเขียนโปรแกรม HyperLogLog

ทีละขั้นตอน:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

ฟังก์ชัน alpha คืนค่าปรับแก้สำหรับค่าประมาณที่คำนวณได้ ซึ่งรู้จักแล้วจากตอนก่อน เพียงแต่ใน HyperLogLog ค่า alpha ขึ้นกับจำนวนกลุ่ม

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

ฟังก์ชันที่คืนจำนวนบิตศูนย์ที่ท้ายจำนวน

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

ฟังก์ชันที่ไล่ดูทุกค่า แบ่งเป็น num_buckets กลุ่ม และคำนวณดัชนีของเลข 1 ตัวแรกจากทางขวาของแต่ละกลุ่ม (ความยาวสูงสุดของส่วนท้ายที่เป็นศูนย์บวกหนึ่ง)

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

ฟังก์ชันสำหรับขั้นตอนวิธี Linear counting ที่ปรับเล็กน้อย

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

ฟังก์ชันหลักที่รวมทุกอย่างเข้าด้วยกัน ขั้นแรกคำนวณค่าประมาณด้วย LogLog ที่ปรับแล้ว ในบรรทัดที่สี่ใช้ค่าเฉลี่ยฮาร์มอนิกแทนค่าเฉลี่ยเลขคณิต และท้ายสุดใช้ Linear counting ปรับแก้ ถ้าค่าประมาณที่คำนวณได้น้อยกว่า 2.5 เท่าของจำนวนกลุ่ม (ในกรณีนี้คาดว่าค่าประมาณมาตรฐานของ LogLog จะแย่กว่าการใช้ Linear counting) และถ้าในอาร์เรย์ของค่าสูงสุดมีศูนย์อย่างน้อยหนึ่งตัว (อาร์เรย์ที่เป็นหนึ่งทั้งหมดใช้ใน Linear counting ไม่ได้ ดูบทความก่อนหน้า) แล้วผลลัพธ์ของ HyperLogLog เป็นอย่างไร

รันโค้ดทดสอบที่ประมาณคาร์ดินัลลิตีของเซตที่มีคาร์ดินัลลิตี 10, 100, …, 1,000,000 ตามลำดับ:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

ผลลัพธ์:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

จะเห็นว่าผลลัพธ์คลาดเคลื่อนจากค่าที่ถูกต้องน้อยกว่าหนึ่งเปอร์เซ็นต์เสมอ ซึ่งดีมาก

การปรับปรุง HyperLogLog เพิ่มเติม

HyperLogLog ได้รับการปรับปรุงที่น่าสนใจเพิ่มเติมอีกหลายอย่าง ปัญหาหนึ่งที่ยังเหลืออยู่คือใช้หน่วยความจำมาก ฟังดูแปลก เพราะคราวก่อนได้ชื่นชมว่าใช้หน่วยความจำน้อย และคำนวณได้ว่าอาร์เรย์ของค่าสูงสุดใช้เพียง 768 ไบต์ แต่ปัญหาเกิดขึ้นเมื่อต้องการคำนวณคาร์ดินัลลิตีไม่ใช่ของมัลติเซตขนาดมหึมาเซตเดียว แต่ของมัลติเซตขนาดเล็กหลายล้านเซตพร้อมกัน หรือเมื่อต้องการเก็บอาร์เรย์ของค่าสูงสุดที่คำนวณได้ไว้ในฐานข้อมูลเพื่อนำไปประมวลผลต่อภายหลัง

เช่น ถ้าคำนวณคาร์ดินัลลิตีของมัลติเซตหนึ่งพันล้านเซตพร้อมกัน ด้วยการเขียนโปรแกรมแบบปัจจุบันจะต้องใช้ 1,000,000,000 คูณ 768 ไบต์ ซึ่งเท่ากับ 768 GB ในแง่หนึ่งก็ไม่เลว … แต่ในอีกแง่หนึ่ง HyperLogLog เขียนโปรแกรมให้ดีกว่านี้ได้

การแทนแบบเบาบาง

สมมติว่าตั้ง k=12 นั่นคือใช้ 12 บิตระบุกลุ่ม จึงได้กลุ่มของค่าแฮชที่ต่างกัน 212 กลุ่ม ตอนเริ่มขั้นตอนวิธีต้องจองอาร์เรย์ความยาว 4,096 (ดูบรรทัดที่ 3 ของฟังก์ชัน count_maxims) และสมมติว่ามัลติเซตมีสมาชิกที่ต่างกันสามตัว หมายความว่าจะกำหนดค่าลงในอาร์เรย์สามตำแหน่ง และอีก 4,093 ค่าในอาร์เรย์จะยังเป็นศูนย์ คือไม่ได้ใช้เลย ซึ่งไม่ค่อยมีประสิทธิภาพนัก

เพื่อเลี่ยงการมีอาร์เรย์ที่ส่วนใหญ่เป็นศูนย์และไม่ได้ใช้ แต่ยังกินหน่วยความจำอันมีค่า ตอนเริ่มต้นอาจเก็บค่าเป็นคู่ [index, value] (ดัชนี ค่า) แทน ตัวอย่างเพื่อให้เข้าใจง่ายขึ้น อาร์เรย์นี้

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

แทนด้วยคู่สองคู่ได้ ซึ่งประหยัดหน่วยความจำกว่ามาก:

[0, 7], [4, 12]

แทนที่จะจองพื้นที่ว่างที่ไม่ได้ใช้จำนวนมากไว้ในหน่วยความจำ ก็จองเพิ่มทีละน้อยเฉพาะพื้นที่ที่ต้องใช้จริง การแทนแบบนี้เรียกว่าการแทนแบบเบาบาง (sparse) อย่างไรก็ตาม ถึงจุดหนึ่งการแทนแบบนี้จะใช้หน่วยความจำมากกว่าการเก็บในอาร์เรย์ เมื่อนั้นก็แปลงการแทนแบบเบาบางเป็นอาร์เรย์ธรรมดาได้โดยไม่สูญเสียข้อมูล

ค่าชดเชย

ในทางปฏิบัติพบว่าค่าทุกค่าในอาร์เรย์ใกล้เคียงกัน อาร์เรย์ของค่าสูงสุดโดยทั่วไปมีลักษณะเช่นนี้:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

ทุกค่าอยู่ราว ๆ 13 อีกวิธีหนึ่งในการลดขนาดของอาร์เรย์เช่นนี้คือ ลบค่าคงตัวค่าหนึ่งออกจากสมาชิกทุกตัวแล้วจำค่านั้นไว้ (ค่าชดเชย หรือ offset) เช่น ลบแปดออก:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

ตอนนี้แต่ละค่าในอาร์เรย์ใช้หน่วยความจำน้อยลง ในอาร์เรย์แรกต้องเก็บจำนวนตั้งแต่ 0 ถึง 15 ซึ่งต้องใช้ 4 บิต ส่วนอาร์เรย์ที่สองใช้ 3 บิตก็พอ เพราะเก็บเพียงจำนวนตั้งแต่ 0 ถึง 7 แน่นอนว่าวิธีนี้ต้องเขียนโปรแกรมอาร์เรย์ในระดับบิต เมื่อต้องการอ่านค่าจากอาร์เรย์ ต้องบวกค่าที่จำไว้กลับเข้าไป

…และยังมีการปรับปรุงอื่น ๆ อีกมาก งานวิจัยในเรื่องนี้ยังดำเนินอยู่ จึงรอคอยแนวคิดใหม่ที่น่าสนใจได้อีก คราวหน้าจะกล่าวถึงยูเนียนและอินเตอร์เซกชันของเวกเตอร์ HyperLogLog และในอนาคตอันใกล้จะกล่าวถึงว่าทำไมการเก็บเวกเตอร์ HyperLogLog นับพันล้านเวกเตอร์จึงอาจมีประโยชน์

ลิงก์และแหล่งอ้างอิง

สารบัญ: Linear counting: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, Min Value: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, LogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกัน, HyperLogLog: การประมาณจำนวนค่าที่ไม่ซ้ำกันอย่างแม่นยำ