How do I benchmark research if there is no previous work against which I can compare it?
A benchmark is a standard or reference that will allow other authors compare their algorithms with yours. If the problem is known and other papers were published to solve it, follow the lead and compare your algorithm with them using the same parameters. If there are no other paper solving the problem, look for similar problems and check how they are described by certain variables. 

The most basic parameter is the problem size, ie how many instances your problem has to deal with. For sorting algorithms, it is the number of items to sort. Usually, we start with quantities that could be easily handled in memory, increase to the limits of available memory, up to numbers that will need disk to store all items.

The second parameter is distribution. Are all instances equally probable and distributed along the possible spectrum? For sorting algorithms, if the set of items is partially sorted or totally random will impact the performance. In my thesis, I worked with geographical objects like cities, which are concentrated in some areas that were difficult to process, and other areas totally empty that could be easily recognized and discarded as not interesting.  

Each problem might have multiple parameters, some are important, others are irrelevant. Your work is to identify them and choose values that are realistic and could show the strengths and weakness for different algorithms, not only yours.

Another set of parameters, very common when comparing software, is related to hardware, like the number of processors, total memory, network speed, etc... 

Hope it helps, without reading your paper is hard to be specific.