Skip to content

Potential incorrect calculation of Auxiliary mtable #1

@utkarshmttl

Description

@utkarshmttl

For k=12, p=0.5, alpha=0.1:

The (unadjusted) mtable: [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4]

For this case, the blocks should be: [0, 0, 0, 1 | 1, 1, 2 | 2, 3 | 3, 3, 4]

which implies that block sizes should be [4, 3, 2, 3]

which is also as described in the paper's Table 3 on page 5.

image

However, the behaviour is different using the code:

image

This seems to be because inside the function compute_aux_mtable(mtable) in fairsearchcore/mtable_generator.py, the loop for position in range(1, len(mtable)): at line 69 goes from range(1,len(mtable) when probably it should go from range(1,len(mtable)+1.

Another case- For k=10, p=0.5, alpha=0.1:

The (unadjusted) mtable: [0, 0, 0, 1, 1, 1, 2, 2, 3, 3]

For this case, the blocks should be: [0, 0, 0, 1 | 1, 1, 2 | 2, 3 | 3]

In this case, should there be

  1. three blocks with sizes [4, 3, 2]
    (in this case the problem is maxProtected would be 4+3+2 = 9, missing 1 candidate as total candidates should be 10.)
    or
  2. three blocks with sizes [4, 3, 3]
    or
  3. four blocks with sizes [4, 3, 2, 1].
    (in this case the problem is that since m(k=10) = 3, total blocks are expected to be 3 and not 4?)

In code behaviour as per point 1 is seen:

image

The change mentioned above (changing the range of loop to include last element) solves the first case (k=12) but not the second case (k=10), for which appropriate changes might need to be made considering what is the expected behaviour - one of points 1, 2 or 3.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions